package com.myjavalab.sort;

import com.myjavalab.util.DataUtil;
import com.myjavalab.util.PrintUtil;

public class ShellSort {

	public static void sort(int[] ary) {
		PrintUtil.prt(ary);
		int interval = getInterval(ary.length);
		while(interval > 0) {
			for(int i = 0; i < interval; i++){				
				for(int j = i+interval; j < ary.length; j+=interval) {
					int cur = ary[j];
					int pre = j - interval;
					while(pre >= i && ary[pre] > cur){
						ary[pre+interval] = ary[pre];
						pre-=interval;
					}
					ary[pre+interval] = cur;
				}

			}
//			PrintUtil.prt(ary);
			interval = (interval-1)/3;
		}
		
	}
	
	private static int getInterval(int size){
		int h = 1;
		while(h < size){
			h = h*3 + 1;
		}
		return (h-1)/3;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] ary = DataUtil.getNumber(100, 10000);
		long startTime = System.currentTimeMillis();
		sort(ary);
		long endTime = System.currentTimeMillis();
		PrintUtil.prt(startTime, endTime);
//		PrintUtil.prt(getInterval(1000));
	}

}
